#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
	//两个都为空
	if (p == NULL && q == NULL)
		return true;
	//其中一个为空
	if (p == NULL || q == NULL)
		return false;
	//值不同
	if (p->val != q->val)
		return false;
	//向下递进继续比较
	return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {

	//root到叶子结点，就代表次子树已经false
	if (root == NULL)
		return false;

	//两个节点相等，才有资格验证从这个节点开始向下是否是相等的树
	if (root->val == subRoot->val)
	{
		if (isSameTree(root, subRoot))
			return true;
	}
	//root及以下不和subRoot相同。就先先比对root的左子树，再比对root的右子树
	return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}